Technical Field
The invention is related to embedded real-time computing systems, and in particular, to automatic self tuning of real-time scheduling and control of interoperation among a plurality distributed real-time components.
Background Art
As semiconductor technology becomes more mature and inexpensive, it becomes feasible to add computing and/or communication capabilities to many devices that used to be mechanical or analog, and to come up with new devices entirely. Computing that enhances existing everyday devices and makes them smarter without requiring extra human interaction is conventionally referred to as “invisible computing.” In this domain the computer is not the main focus but rather the device itself or the specialized function it performs.
For example, devices used in “invisible computing” environments include embedded control systems, including consumer devices, intelligent sensors and smart home controls; communication-oriented devices such as digital cell phones and networking infrastructure; programmable peripherals and microcontrollers, home appliances, toys, games, etc. In all these cases, the devices typically include inexpensive microprocessors, such as a DSP, a VLIW, or a micro-controller rather than a general-purpose computing capability or platform (such as a PC-type computer). One problem with such devices, relative to a general-purpose computing platform is that the available system memory is typically severely restricted; there might be no MMU; and network connections might be sporadic. However, given these limitations, there is still an essential requirement for real-time interoperability, operation, and control.
Invisible computing differs from personal computing mainly because the user interface is not screen and keyboard based, and resources (such as energy, memory, bandwidth, etc.) are often severely restricted. While a PC or workstation can use a general-purpose operating system (a collection of commonly needed features) an invisible computer can seldom afford such luxury because of its severely constrained resources. Consequently, software controlling such devices is generally specifically tailored to the specific applications that are to be performed by such devices.
Invisible computing is also slightly different from traditional embedded computing in that the devices are most often communicating with each other and/or with general-purpose computers (via either wired or wireless connections) acting as a central controller/scheduler, and have a limited power supply.
Limited resource, semi-intelligent devices found in invisible computing environments can perform rudimentary tasks autonomously. It is the ability to communicate with other invisible devices that gives them added capabilities, such that the value of the whole system is greater than the sum of its parts.
When the small devices have the ability to communicate with PCs or other “big machines” in addition to other peers, it is possible to leverage the advantages of invisible computing in desktop computing and vice versa. PCs can provide backend processing for small devices, and small devices can extend the reach of a traditional PC further into our everyday lives. For example, a small device can access a database on a web server; a PC can provide a user interface for examining and analyzing sensor data in a home; etc.
One area where conventional invisible computing environments are lacking deals with the ability to handle concurrent tasks given limited resources. For example, one common solution for handling concurrent tasks spread among two or more devices is to provide a proportional time schedule that simply reserves x % of the CPU cycles [or bandwidth] in y-second intervals for particular devices. Conventional “constraint-based scheduling” (CBS) techniques and related “earliest deadline first” (EDF) techniques have also been used for handling concurrent computational tasks given limited resources.
For example, one conventional invisible computing system, termed “MMLite” provides a constraint-based real-time scheduler with feedback to dispatch threads. The programmer dynamically provides the scheduler with information about the time constraints under which a certain section of code is to be executed. The scheduler will make sure that the thread is scheduled before the given deadline with enough projected time to complete the indicated computing. To prevent priority inversion, the currently running thread's constraints are inherited by other threads that might block it. However, as with the previous example, the constraint scheduler schedules threads in a time-sharing fashion. Time-sharing is internally implemented using artificial constraints. Threads that specify time constraints are given priority over all time-sharing threads. Unfortunately, while such solutions are generally sufficient for simple application behaviors, they cannot effectively deal with: 1) a mix of repetitive and one-time jobs; and 2) cases where the work needs to be done within a constrained sub-interval, including both temporal and spatial issues.
Similar ideas exist with respect to industrial quality controls. For instance, in an example of automated automobile manufacturing, an assembly line stops for 10 seconds every minute. Robotic welding of a door handle takes 4 seconds. Seemingly, this is plenty of time to complete the welding task. However, if the robot welds a door handle outside the correct time window, it might destroy the car. Consequently, the proportional time schedule noted above would not work by itself. Therefore, in this case, various sensors typically ensure that the car is in the correct position for the door handle to be welded so as to avoid costly errors. Unfortunately, because checks need to be made as to correct handle position prior to every welding operation, advance planning and resource sharing becomes a more difficult proposition. Consequently, conventional industrial quality control methods are not readily adaptable for use in real-time control and scheduling of distributed devices connected in an ad-hoc network environment.